/*
 https://leetcode.cn/problems/min-cost-climbing-stairs/solutions/528955/shi-yong-zui-xiao-hua-fei-pa-lou-ti-by-l-ncf8/
 */
class Solution {
public:
    int minCostClimbingStairs(vector<int>& cost) {
        // 获取楼梯的总阶数，即成本数组的长度
        int n = cost.size();

        // 创建一个 dp 数组，大小为 n + 1，用于存储到达每一阶梯的最小成本
        vector<int> dp(n + 1);

        // 初始化 dp 数组
        // dp[0] 表示从楼梯的底部（虚拟第 0 阶）开始的最小成本，这里设为 0
        // dp[1] 表示从第 1 阶开始的最小成本，这里也设为 0
        dp[0] = dp[1] = 0;

        // 从第 2 阶开始，遍历到第 n 阶，计算到达每一阶梯的最小成本
        for (int i = 2; i <= n; i++) {
            // dp[i] 表示到达第 i 阶梯的最小成本
            // 可以从 i-1 阶梯跳到 i 阶梯，或者从 i-2 阶梯跳到 i 阶梯
            // 计算这两种情况的最小值，然后加上当前阶梯的成本
            dp[i] = min(dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i - 2]);
        }

        // 返回到达最后一阶的最小成本
        // 由于我们允许从第 n-1 或第 n-2 阶直接跳到终点，所以 dp[n] 存储的即为所求的最小成本
        return dp[n];
    }
};
